[Coding014] LeetCode 21

Merge Two Sorted Lists

More coding records

Get the knowledge flowing and circulating! :)

目录

※ 本题收获

归并排序思想

• 一个while

• 两个if

题目：21. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

xxxxxxxxxx
2
1
Input: list1 = [1,2,4], list2 = [1,3,4]
2
Output: [1,1,2,3,4,4]

Example 2:

xxxxxxxxxx
2
1
Input: list1 = [], list2 = []
2
Output: []

Example 3:

xxxxxxxxxx
2
1
Input: list1 = [], list2 = [0]
2
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].

• -100 <= Node.val <= 100

• Both list1 and list2 are sorted in non-decreasing order.

代码

xxxxxxxxxx
56
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
13
        // 基本情况的判定
14
        if (list1 == null && list2 == null) return null;
15
        if (list1 == null) return list2;
16
        if (list2 == null) return list1;
17

18
        // 结果链表，最后返回的是：dummy.next; (经典操作)
19
        ListNode dummy = new ListNode(0);
20
        // 让r指向dummy，这样就让r冲锋中前，dummy稳坐军营即可！
21
        ListNode r = dummy;
22

23
        // p, q分别作为指针操作待合并的两个链表
24
        ListNode p = list1;
25
        ListNode q = list2;
26

27
        // 如果都还不为空的时候，就开始一个一个比较；
28
        while (p != null && q != null)
29
        {
30
            if (p.val <= q.val)
31
            {
32
                r.next = p;
33
                p = p.next;
34
            }
35
            else
36
            {
37
                r.next = q;
38
                q = q.next;
39
            }
40
            r = r.next;
41
        }
42

43
        // 如果有一个已经完全插入到结果链表，而另一个还剩点尾巴的时候，直接接上
44
        if (p != null)
45
        {
46
            r.next = p;
47
        }
48

49
        if (q != null)
50
        {
51
            r.next = q;
52
        }
53

54
        return dummy.next;
55
    }
56
}

复杂度分析

$O(max(m+n))$$O(max(m+n))$

m: list1的长度；

n: list2的长度。